import java.util.Stack;

/**
 * Created with IntelliJ IDEA.
 * Description :
 * User: $ {USER}
 * Date: $ {YEAR}-$ {MONTH}一$ { DAY}
 * Time: ${ TIME}
 */
public class Test {
    TreeNode root;
    TreeNode p;
    TreeNode q;
    public void createTree() {
        root = new TreeNode(37);
        root.left = new TreeNode(-34);
        root.right = new TreeNode(-48);
        root.left.right = new TreeNode(-100);
        root.right.left = new TreeNode(-101);
        p = root.right.right = new TreeNode(48);
        root.right.right.left = new TreeNode(-54);
        q = root.right.right.left.left = new TreeNode(-54);
    }


    // public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
    //     // 在递归去寻找的过程中可能会出现下面两种情况（限制条件）
    //     if (root == null) {
    //         return null;
    //     }
    //     if (root == q || root == p) {
    //         return root;
    //     }
    //     // 走到这里说明根结点一定不存在，则判断左子树和右子树即可
    //     // 遍历左子树
    //     TreeNode leftTree = lowestCommonAncestor(root.left, p, q);
    //     // 遍历右子树
    //     TreeNode rightTree = lowestCommonAncestor(root.right, p, q);
    //     // 再遍历完成之后，我们就来判断是哪种情况
    //     if (leftTree != null && rightTree != null) {
    //         return root;
    //     }
    //     if (leftTree != null && rightTree == null) {
    //         return leftTree;
    //     }
    //     if (leftTree == null && rightTree != null) {
    //         return rightTree;
    //     }
    //     return null;
    // }

    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        Stack<TreeNode> stackP = new Stack<>();
        Stack<TreeNode> stackQ = new Stack<>();
        getPath(root, p, stackP);
        getPath(root, q, stackQ);
        // 先让长的走差值步数
        if (stackP.size() > stackQ.size()) {
            int size = stackP.size() - stackQ.size();
            while (size-- > 0) {
                stackP.pop();
            }
        } else {
            int size = stackQ.size() - stackP.size();
            while (size-- > 0) {
                stackQ.pop();
            }
        }
        // 开始一起出
        while (stackQ.peek() != stackP.peek()) {
            stackQ.pop();
            stackP.pop();
        }
        // while (!stackQ.isEmpty()) {
        //     if (stackQ.peek() == stackP.peek()) {
        //         return stackP.peek();
        //     } else {
        //         stackQ.pop();
        //         stackP.pop();
        //     }
        // }
        return stackQ.peek();
    }

    private TreeNode getPath(TreeNode root, TreeNode target, Stack<TreeNode> stack) {
        if (root == null) {
            return null;
        }
        stack.push(root); // 先得把这个入栈
        if (root == target) {
            return root;
        }
        // 左子树
        TreeNode leftTree = getPath(root.left, target, stack);
        if (leftTree != null) { // 左子树不为null，说明在左子树找到了，即返回
            return leftTree;
        }
        // 右子树
        TreeNode rightTree = getPath(root.right, target, stack);
        if (rightTree != null) {
            return rightTree;
        }
        // 左右子树的遍历结果都是null，即都没找到，就出栈
        if (leftTree == null && rightTree == null) {
            stack.pop();
        }
        return null;
    }
}

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode() {
    }

    TreeNode(int val) {
        this.val = val;
    }

    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}